package com.gxc.string;


/**
 * 最长公共子序列
 *
 * 解法：
 * dp
 * dp[i][j] 表示 str1 以i结尾和  str2 以 j结尾的最长公共子序列长度
 *
 * 如果 str1[i]=str2[j], 则 dp[i][j] =dp[i-1][j-1]+1;
 * 如果 str1[i]!=str2[j], 则 dp[i][j] = max(dp[i-1][j] , dp[i][j-1] );
 *
 */
public class LongestCommonSubsequence {

    public static void main(String[] args) {
        String str1 ="13542687";
        String str2 ="148675";
        System.out.println(process(str1, str2));
        System.out.println(processStr(str1, str2));

        str1 = "mhunuzqrkzsnidwbun";
        str2 = "szulspmhwpazoxijwbq";
        System.out.println(process(str1, str2));
        System.out.println(processStr(str1, str2));
        System.out.println(process2(str1, str2));

    }

    public static int process(String str1, String str2) {
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int l1 = str1.length();
        int l2 = str2.length();

        int[][] dp = new int[l1+1][l2+1];

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                if (chars1[i-1] == chars2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        return dp[l1][l2];
    }

    /**
     * 压缩空间
     * @param str1
     * @param str2
     * @return
     */
    public static int process2(String str1, String str2) {
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int l1 = str1.length();
        int l2 = str2.length();

        int[] dp = new int[l2+1];

        int leftTop = 0;
        int temp = 0;
        for (int i = 1; i <= l1; i++) {
            //每次换行。leftTop都重0开始
            leftTop = 0;
            for (int j = 1; j <= l2; j++) {
                temp = dp[j];
                if (chars1[i-1] == chars2[j-1]) {
                    dp[j] = leftTop+1;
                }
                else {
                    dp[j] = Math.max(dp[j-1], dp[j]);
                }
                leftTop = temp;
            }
        }
        return dp[l2];
    }

    public static String processStr(String str1, String str2) {
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int l1 = str1.length();
        int l2 = str2.length();

        int[][] dp = new int[l1+1][l2+1];

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                if (chars1[i-1] == chars2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        int max = dp[l1][l2];

        StringBuffer str = new StringBuffer();
        while (max>0) {
            if (dp[l1][l2] == dp[l1-1][l2]) {
                l1--;
            } else if (dp[l1][l2] == dp[l1][l2-1]){
                l2--;
            } else {
                str.append(chars1[l1-1]);
                l1--;
                l2--;
                max--;
            }
        }
        //字符反转
        str.reverse();
        return str.toString();
    }

}
